package airthmetic.exercise.search;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _37_解数独 {

    Set<Character>[] rowSet;
    Set<Character>[] colSet;
    Set<Character>[] blockSet;

    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }



        rowSet = new HashSet[9];
        colSet = new HashSet[9];
        blockSet = new HashSet[9];
        for(int i=0; i<9; i++){
            rowSet[i] = new HashSet();
            colSet[i] = new HashSet();
            blockSet[i] = new HashSet();
        }
        List<int[]> list = new ArrayList();

        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] != '.'){
                    rowSet[i].add(board[i][j]);
                    colSet[j].add(board[i][j]);
                    int blockIndex = (i / 3) * 3 + j / 3;
                    blockSet[blockIndex].add(board[i][j]);
                }else{
                    list.add(new int[]{i,j});
                }
            }
        }

        backtrack(0,list.size(),board,list);
    }

    public boolean backtrack(int dept, int end, char[][] board, List<int[]> list){
        // terminal
        if(dept == end){
            return true;
        }
        int[] cur = list.get(dept);
        int row = cur[0];
        int col = cur[1];
        int block = (row / 3) * 3 + col / 3;
        // process current logic0
        for(char c='1'; c<='9'; c++){
            if(rowSet[row].contains(c)){
                continue;
            }
            if(colSet[col].contains(c)){
                continue;
            }
            if(blockSet[block].contains(c)){
                continue;
            }

            board[row][col] = c;
            rowSet[row].add(c);
            colSet[col].add(c);
            blockSet[block].add(c);

            boolean b = backtrack(dept+1, end, board, list);
            if(b){
                return true;
            }
            board[row][col] = '.';
            rowSet[row].remove(c);
            colSet[col].remove(c);
            blockSet[block].remove(c);
        }

        return false;
    }


    public void solveSudoku2(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }

        rowSet = new HashSet[9];
        colSet = new HashSet[9];
        blockSet = new HashSet[9];

        for(int i=0; i<9; i++){
            rowSet[i] = new HashSet();
            colSet[i] = new HashSet();
            blockSet[i] = new HashSet();
        }
        List<int[]> list = new ArrayList<>();
        for(int i=0; i<9; i++){
           for(int j=0; j<9; j++){
               if (board[i][j] == '.'){
                   list.add(new int[]{i,j});
               }else{
                   rowSet[i].add(board[i][j]);
                   colSet[j].add(board[i][j]);
                   int blockIndex = (i / 3) * 3 + j / 3;
                   blockSet[blockIndex].add(board[i][j]);
               }
           }
        }

        int size = list.size();
        backtrack2(list,size,0,board);

    }

    private boolean backtrack2(List<int[]> list, int size, int dept, char[][] board) {
        if(dept == size){
            return true;
        }
        int[] ints = list.get(dept);
        int x = ints[0];
        int y = ints[1];
        int blockIndex = (x / 3) * 3 + y / 3;
        for(char c='1'; c<='9'; c++){
            if(rowSet[x].contains(c)){
                continue;
            }
            if(colSet[y].contains(c)){
                continue;
            }
            if(blockSet[blockIndex].contains(c)){
                continue;
            }

            board[x][y] = c;
            rowSet[x].add(c);
            colSet[y].add(c);
            blockSet[blockIndex].add(c);

            boolean b = backtrack2(list,size,dept+1, board);
            if (b) {
                return true;
            }
            board[x][y] = '.';
            rowSet[x].remove(c);
            colSet[y].remove(c);
            blockSet[blockIndex].remove(c);


        }
        return false;
    }


    public static void main(String[] args) {
        _37_解数独 v = new _37_解数独();
        char[][] board = {{'5','3','.','.','7','.','.','.','.'},
                        {'6','.','.','1','9','5','.','.','.'},
                        {'.','9','8','.','.','.','.','6','.'},
                        {'8','.','.','.','6','.','.','.','3'},
                        {'4','.','.','8','.','3','.','.','1'},
                        {'7','.','.','.','2','.','.','.','6'},
                        {'.','6','.','.','.','.','2','8','.'},
                        {'.','.','.','4','1','9','.','.','5'},
                        {'.','.','.','.','8','.','.','7','9'}};
        v.solveSudoku(board);

        for (int i=0; i<board.length; i++){
            for (int j=0; j<board[0].length; j++){
                System.out.print(board[i][j]);
            }
            System.out.println();
            System.out.println("============================================");
        }

    }

}
